package JZOffer;

import java.util.HashMap;

/**
 * @author Lw中
 * @date 2021/7/30 23:08
 */
public class Jz10 {

//    Jz10 I.斐波那契数列

    // 方法一：使用递归
//    public int fib(int n) {
        // 超出时间限制
//        if (n == 0) return 0;
//        if (n == 1 || n == 2) return 1;
//        return fib(n - 1) + fib(n - 2);
//    }

    // 方法二：使用递归 + map集合去掉重复计算
    HashMap<Integer, Integer> map = new HashMap();
    public int fib(int n) {
        if (n < 3) {
            if (n == 0) return 0;
            if (n == 1 || n == 2) return 1;
        }
        if (map.containsKey(n)) {
            // 如果计算过直接返回结果
        } else {
            // 没有计算过，递归计算,并且把结果保存到map中
            map.put(n,(fib(n-1) + fib(n-2))% 1000000007);
        }
        return map.get(n);
    }

}
